![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
Table 7.5 shows the results of measuring this same property in a different way. Instead of requiring a run of n consecutive identical differences, this metric is similar to a mini-DPmax, computed over only the 20 input values used in the subkey generation (e.g., 0, 2, 4, . . ., 38). The quantity measured is the maximum number of equal differences out of the 20 values generated, across key pairs. In other words, while it may be difficult to generate a large run, it may be possible to generate equal values in a large (non-consecutive) fraction of the set of differences. However, the results are again very encouraging, showing that it is extremely difficult to force more than five or six differences to be identical. This also shows that it is not possible to influence only a few Ai, as that would require many zero differences.
Comparison to Random S-boxes. For every metric discussed here, a similar distribution using randomly generated 8-bit permutations has been generated for purposes of comparison. For example, DPmax was computed for a set of 216 randomly generated permutations, and the resulting distribution of DPmax values was compared to that of the Twofish key-dependent S-boxes. For each metric, the probability distributions looked virtually identical to those obtained for the Twofish set of key-dependent S-boxes, except for small fluctuations on the tail ends of the distribution, as should be expected. This similarity is comforting, as is the fact that the probability distributions for each metric look quite similar across key sizes. These results help confirm our belief that, from a statistical standpoint, the Twofish S-box sets behave largely like a randomly chosen set of permutations.
The four bytes output from the four S-boxes are multiplied by a 4-by-4 MDS matrix over GF(28). This matrix multiply is the principal diffusion mechanism in Twofish. The MDS property guarantees that the number of changed input bytes plus the number of changed output bytes is at least five. In other words, any change in a single input byte is guaranteed to change all four output bytes; any change in any two input bytes is guaranteed to change at least three output bytes; and so forth. More than 2127 such MDS matrices exist, but the Twofish MDS matrix is also carefully chosen with the property of preserving the number of bytes changed even after the rotation in the round function.
The MDS matrix used in Twofish has fixed coefficients. Initially, some thought was given to making the matrix itself key dependent, but such a scheme would require the verification that the key-dependent values in fact formed an MDS matrix, adding a non-trivial computational load to the key selection and key scheduling process. However, it should be noted that there are many acceptable MDS matrices, even with the extended properties discussed below.
For software implementation on a modern microprocessor, the MDS matrix multiply is normally implemented using four lookup tables, each consisting of 256 32-bit words, so the particular coefficients used in the matrix do not affect performance. This works because the actual transformation defined by the MDS matrix is purely linear over GF(2). That is, each of the output bits is the XOR of a subset of the input bits and hence we can XOR four table lookups together to compute the entire 32-bit word. However, for smart cards and in hardware, simple coefficients, as in Square [DKR97], can make implementations cheaper and faster.
Unlike the MDS matrix used in Square, Twofish does not use the inverse matrix for decryption because of its Feistel structure, nor is there a requirement that the matrix be a circulant matrix. However, because of the rotation applied after the XOR within the round function, it is desirable to select the MDS matrix carefully to preserve the diffusion properties even after the rotation. For both encryption and decryption, a right rotation by one bit occurs after the XOR. This direction of rotation is chosen to preserve the MDS property with respect to the PHT addition a + 2b, since the rotation undoes the shift applied to b as part of the PHT. It is true that the most significant bit of b is still lost in this half of the PHT, but the MDS properties for three of the bytes are still fully guaranteed with respect to b, and they are met with probability 254/255 for the fourth byte.
The effect of the rotation on the unshifted PHT additions also needs to be addressed. A single byte input change to the MDS matrix will change all four output bytes, which affect the round function output, but after rotation there is no such guarantee. If a byte value difference of 1 is one output from the matrix multiply, performing a 32-bit rotate on the result will shift in one bit from the next byte in the 32-bit word and shift out the only non-zero bit. The MDS matrix coefficients in Twofish are carefully selected so that, if a byte difference 1 is output from the matrix multiply with a single byte input change, the next highest byte is guaranteed to have its least significant bit changed as well. Thus, if the rotation shifts out the only original flipped bit, it will also shift in a flipped bit from the next byte.
The construction used to preserve this property after rotation is actually very simple. The idea is to choose a small set of non-zero elements of GF(28) with the property that, for each pair x, y in the set, if x*a = 1, then y*a (i.e., y/x) has the least significant bit set. We then use such a set as the coefficients to construct an MDS matrix. Observe that this property is reflexive; i.e., if x = y, then y/x = 1, so the property holds. It is intuitively obvious (and empirically verified) that the probability that two random field elements satisfy this property is roughly one half, so it should not be difficult to find such sets of elements. Also, since over 75 percent of all 4-by-4 matrices over GF(28) are MDS, the hope of finding such a matrix sounds reasonable.
A computer search was executed over all primitive polynomials of degree eight, looking for sets of three simple elements x,y,z with the above property. Simple in this context means that x * a for arbitrary a can be easily computed using at most a few shifts and XORs. Several dozen sets of suitable values were found, each of which allowed several MDS matrices with the three values. The primitive polynomial v(x) = x8 + x6 + x5 + x3 + x0 was selected, together with the field elements 01, EF, and 5B (using hexadecimal notation and the field element to byte value correspondence of Chapter 4). The element EF is actually ß2 + ß1 + 1, where ß is a root of v(x), and 5B is ß2 + 1, so multiplication by these elements consists of two LFSR right shifts mod v(x), plus a few byte XORs.
Previous | Table of Contents | Next |